1. Field of the Invention
The present invention relates to the field of computer networking, and more specifically to an AND-OR multi-cast message routing method for high performance fault-tolerant message replication.
2. Related Art
In many high availability distributed service environments, it is required to maintain multiple synchronized databases with nodes spread over multiple local area network (LAN) sites connected to a Wide Area Network (WAN). High performance requirements mandate that these databases synchronize in real-time continually with new update messages originating at any node in the configuration.
Some terms are defined hereunder along with FIGS. 1-4 for a better understanding of the invention.
FIG. 1 illustrates a typical multi-site nodal architecture. In this example, LANs 11, 12, 13, are connected to a WAN 16. Each LAN 11, 12, 13, is housing Service Control Points (SCPs) and corresponding databases (DB). The SCPs receive updates from an SS7 network 17 and are further required to replicate their share of SS7 Network Side Updates (NSUs), and propagate the updates to all their peer nodes for commitment to their respective databases for an automatic synchronization.
In the configuration of FIG. 1, all the SCPs have access to their own copies of service databases for query processing and updating. Each SCP communicates the received updates to other SCPs so that they may commit the updates to the respective databases. The databases thus get up-to-date, as well as synchronized on the service information.
The message replication process implies that each message is copied and transmitted to all other destinations. It can be implemented usingxe2x80x94synchronous or asynchronous algorithms. The goal of the synchronous class of algorithms is message-by-message synchronization, whereby a message is transmitted only after the previously propagated message is confirmed to have been successfully committed at all the destinations. In addition, a message has to be committed either everywhere or nowhere, and if the message cannot be committed at one SCP, the transaction is rolled back and all the databases are restored to the previous state. Obviously the synchronous algorithms are limited by the speed of the slowest SCP.
Another disadvantage of this class of algorithms is that, occasionally, an SCP may fail and may hold up the entire replication process until it is revived. In order to guarantee that the updates are carried out atomically, i.e. done everywhere or nowhere, exchange of a large number of protocol messages among SCPs is required and this adversely impacts the network bandwidth utilization.
FIG. 2 illustrates an example of asynchronous message replication viewed as a process of identical message streams 26, 27, 28, propagating from a source to different destinations 21, 22, 23, at different paces, depending upon the individual destination. The messages are propagated continuously to the peer-SCPs which in turn commit these messages to their respective databases for eventual synchronization of the databases.
Asynchronous algorithms on the other hand, do not guarantee dynamic convergence of the databases, but offer speed and effective network bandwidth utilization, with eventual convergence of the databases. Further, since the time order of origination of the NSUs coming from different sources need not to match the order of their receipt at the destination ends, asynchronous algorithms have to implement a database updating strategy which ensures database synchronization despite the differences in the order in which updates from different streams arrive at individual destination nodes. This update strategy should also involve a method of detecting conflicting updates originating at the same time, or almost at the same time at different SCPs, assuming the clocks of all SCPs are synchronized using a Global Positioning System. Such strategies are available and hence it is possible to implement an asynchronous replication algorithm and take advantage of the high performance it provides. However, it is possible to improve this performance with respect to network bandwidth utilization by effective propagation of message streams.
A solution to the message replication problem is to replicate all the messages received by a SCP and to send them to all the SCPs in the network. The messages generated at any source node are placed into a number of message streams equal to the number of destinations and propagated to their destinations. This implies that the WAN traffic increases five times for the topology with five nodes per LAN site presented in FIG. 1, since a message generated at one node at a LAN site 11 flows five times on each WAN connection. This is definitely a colossal wastage of WAN bandwidth because the same message has to be propagated over a WAN 16 a number of times equal to the number of the other SCPs at all the other LAN sites 12, 13.
Some of the problems associated with such a distribution are listed below. In the usual configuration where a number of SCPs are housed on a few LAN sites interconnected by a WAN, known multi-cast routing methods generate WAN peak traffic proportionate to the number of the SCPs in the network. This could lead to network congestion during traffic periods, because of the relatively low bandwidth of the WANs (compared to the LANs).
To build a fault tolerant process upon the above described framework it would be extremely difficult because if a SCP fails, the replication process stops. Moreover, the complexity of the protocols needed to assess the best SCP to be contacted by a failed node at the time of recovery provides for extensive delay.
Finally, the presently known commercial products use synchronous replication methods like the 2-phase or the 3-phase protocols and this implies extensive protocol message traffic and propagation latency.
Therefore, there is a need for an improved asynchronous replication process for a multi-cast messaging framework.
It is an object of the present invention to provide an asynchronous multi-casting method which alleviates totally or in part the drawbacks of the prior art methods.
Another objective of the present invention is to minimize WAN traffic by allowing a message to flow across a WAN connection at most once during normal, failure-free operation mode.
According to one aspect of the present invention, a multi-cast routing method for asynchronous propagation for messages from any source location to its pre-configured replication nodes in an advanced intelligent network (AIN), is provided. The method comprises the steps of establishing connections between a primary replication node located at a first LAN site and all its peer nodes at same LAN site, creating a transit node located at a second LAN site, and establishing a connection between the primary replication node and the transit node (AND-routing). The transit node becomes a secondary source of replication at the second LAN site. Finally, connections are established between the transit node and all its peer nodes located at the second LAN site.
According to another aspect of the invention, a fault tolerant replication method without any degradation of the WAN bandwidth efficiency, is provided. A surrogate node is created for each replication node so as to form complementary replication nodes at each LAN site. Using an OR-routing, the messages from an active replicator can be directed either to the replication node, or to its surrogate node, whichever is live.
The message streams between replication nodes are established by implementing identical multi-cast queues for each replication node. A multi-cast queue may have a plurality of source sublocations configured at the input end, and a plurality of destination sublocations configured at the output end for routing messages between the replication nodes and the destination nodes that receive the message. The destination nodes contain identical databases as the replication nodes, and use the update messages to synchronize their respective databases with those of the replication nodes. The availability of multiple redundant synchronized databases facilitates implementation of the query load sharing algorithms, and provides for improved fault tolerance, including catastrophe tolerance.
The invention provides an efficient and robust distribution method of services, and allows to maintain a reliable single common view of a user""s data, across multiple databases, without excessive delays or computational overhead. For example, it may be used for updating the Prepaid-card customer""s account balance throughout a network.
An effective utilization of WAN bandwidth is achieved according to the present method at the expense of LAN bandwidth, as the WAN traffic is limited to the size of the message stream, and the total number of LAN sites. Only one connection among the primary and secondary sources of replication is active at one time and therefore, WAN traffic does not increase. Since the WAN traffic is a node limited resource compared to LAN bandwidth, this aspect of the invention is considered to be very advantageously for message replication.
Furthermore, the asynchronous message replication method according to the invention provides better propagation latency and relatively negligible protocol message traffic. WAN traffic reduction is obtained through a process of effective propagation of a stream of messages to all nodes in the network. The relay process involving message replication from primary to secondary sources of replication (AND-routing), and then from secondary sources to the end destinations, distributes the computational burden for multi-casting over a number of nodes since the originating source node need not replicate directly to all the nodes in the network.
Another advantage of this invention is that failures are localized at LAN sites since a reviving node does not need to get the backlog messages across the WAN from the primary source, and can procure them from the secondary source established at the same LAN site.
In addition, this method provides an efficient solution for sensing the death/revival of a node and allows dynamically switching the connection (through OR-routing) of the main replicator with the failed transit node to the surrogate node, and vice-versa.
The method of the present invention is user configurable and allows for deleting nodes, or adding new nodes/sites and bringing them into the replication framework.